#include <iostream>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <climits>
#include <math.h>
#include <queue>
#include <string>

using namespace std;

//test for binary search tree
//left<=parent<=right
struct Node{
        Node* parent;
        Node* left;
        Node* right;
        int val;
        pthread_mutex_t lock;
        Node (Node* m_parent = NULL, Node* m_left = NULL, Node* m_right = NULL, int m_val = INT_MIN) 
        : parent(m_parent), left(m_left), right(m_right), val(m_val){}
};


class bstree{
  public: 
        bstree(){} 
        ~bstree(){destroy();} 
        void insert(int val);
        Node* search(int val);
        bool remove(int val);
        void destroy();
        void print();
        Node* find_min(Node* psuedo_root);
        Node* find_max(Node* psuedo_root);
        
  private:
        bool remove(Node*);
        void insert(int val, Node* leaf);
        Node* search(int val, Node* leaf);
        //bool remove(int val, Node* leaf);
        void destroy(Node* leaf);
        
        Node* root;
};
